package com.heima.leetcode.practice;

/**
 * leetcode 1013. 将数组分成和相等的三个部分
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/1 8:14
 */
public class E1013 {

    /**
     * <h3>方法一：穷举法，耗时高</h3>
     * @param arr 指定数组
     * @return 是否能分为三个相等的部分
     */
    public boolean canThreePartsEqualSum1(int[] arr) {
        int sumPart1 = 0;
        int sumPart2 = 0;
        int init = sum(arr, 1, arr.length - 1); // 多计算了一个1索引处的数，方便后续处理
        int sumPart3 = init;
        for (int i = 0; i < arr.length; i++) {
            sumPart1 += arr[i];
            for (int j = i + 2; j < arr.length; j++) {
                sumPart2 += arr[j - 1];
                sumPart3 -= arr[j - 1];
                if (sumPart1 == sumPart2 && sumPart2 == sumPart3){
                    return true;
                }
            }
            sumPart2 = 0;
            if (i < arr.length - 1) {
                init = init - arr[i + 1];
            }
            sumPart3 = init;
        }
        return false;
    }

    /**
     * 指定范围求和
     * @param arr 数组
     * @param begin 开始索引（包含）
     * @param end 结束索引（包含）
     * @return 求和结果
     */
    private int sum(int[] arr, int begin, int end){
        int sum = 0;
        for (int i = begin; i <= end; i++) {
            sum += arr[i];
        }
        return sum;
    }

    /**
     * <h3>方法二：总和均分，处理不了有负数的情况</h3>
     * @param arr 指定数组
     * @return 是否能分为三个相等的部分
     */
    public boolean canThreePartsEqualSum2(int[] arr) {
        // 1、计算总和
        int totalSum = 0;
        for (int i : arr) {
            totalSum += i;
        }
        // 2、均分三部分
        // 2.1、不能均分返回false
        if (totalSum % 3 != 0){
            return false;
        }
        // 2.2、均分
        int average = totalSum / 3;
        // 3、找到第一部分
        int index = 0;
        int sum = 0;
        while (sum < average){
            sum += arr[index++];
        }
        // 3.1、没找到第一部分，返回false
        if (sum != average){
            return false;
        }
        // 3.2、找到了继续找第二部分
        else {
            // 4、找到第二部分
            sum = 0;
            while (sum < average){
                sum += arr[index++];
            }
            // 4.1、 找到则返回true
            // 4.2、 没找到返回false
            return sum == average;
        }
    }

    /**
     * <h3>方法三：总和均分，能处理有负数的情况，效率最高</h3>
     * @param arr 指定数组
     * @return 是否能分为三个相等的部分
     */
    public boolean canThreePartsEqualSum3(int[] arr) {
        // 1、计算总和
        int totalSum = 0;
        for (int i : arr) {
            totalSum += i;
        }
        // 2、均分三部分
        // 2.1、不能均分返回false
        if (totalSum % 3 != 0){
            return false;
        }
        // 2.2、均分
        int average = totalSum / 3;
        // 3、遍历数组，挨个求和，统计average出现的次数
        int count = 0;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (sum == average){
                count++;
                sum = 0;
                if (count == 2 && i != arr.length - 1){ // 要除开只出现两次的情况，例如 1，-1， 1， -1
                    return true;
                }
            }
        }
        return false; // 如果这里是用最终的count来返回结果，要写成count >= 3因为 0，0，0，0这类情况
    }

    /**
     * <h3>方法四：双指针法，处理不了average为0的情况</h3>
     * @param arr 指定数组
     * @return 是否能分为三个相等的部分
     */
    public boolean canThreePartsEqualSum4(int[] arr) {
        // 1、计算总和
        int totalSum = 0;
        for (int i : arr) {
            totalSum += i;
        }
        if (totalSum % 3 != 0){
            return false;
        }
        int average = totalSum / 3;
        // 2、前后两个指针，分别代表第一部分的最后一个元素，第三部分的第一个元素
        int left = 0;
        int right = arr.length - 1;
        // 3、是否能均分三部分
        int sumLeft = 0;
        int sumRight = 0;
        while (left < right) {
            // 计算左部分的和
            while (left < arr.length && sumLeft != average) {
                sumLeft += arr[left++];
            }
            // 计算右部分的和
            while (right >= 0 && sumRight != average) {
                sumRight += arr[right--];
            }
            // 检查是否满足条件
            if (sumLeft == average && sumRight == average) {
                return left <= right; // 检查中间部分是否存在
            }
        }
        return false;
    }
}
